#include<vector>
#include<algorithm>
using namespace std;
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
    int m=group.size();
    //dp[i][j][k] 0~i p至少为j g不超过k的方法数
    vector<vector<vector<int>>>dp(m+1,vector<vector<int>>(minProfit+1,vector<int>(n+1,0)));
    for(int k=0;k<=n;k++) dp[0][0][k]=1;
    for(int i=1;i<=m;i++){
        for(int j=0;j<=minProfit;j++){
            for(int k=0;k<=n;k++){
                dp[i][j][k]=dp[i-1][j][k];
                if(k-group[i-1]>=0){
                    dp[i][j][k]+=dp[i-1][max(0,j-profit[i-1])][k-group[i-1]];
                }
                dp[i][j][k]%=((long long)1e9+7);
            }
        }
    }
    return dp[m][minProfit][n];
}
class Solution {
public:
    //空间优化 降低一维 通过观察状态依赖修改遍历顺序
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int m=group.size();
        //dp[i][j][k] 0~i p至少为j g不超过k的方法数
        vector<vector<int>>dp(minProfit+1,vector<int>(n+1,0));
        for(int k=0;k<=n;k++) dp[0][k]=1;
        for(int i=1;i<=m;i++){
            for(int j=minProfit;j>=0;j--){
                for(int k=n;k>=group[i-1];k--){
                    dp[j][k]=(dp[j][k]+dp[max(0,j-profit[i-1])][k-group[i-1]])%((long long)1e9+7);
                }
            }
        }
        return dp[minProfit][n];
    }
};